package computation;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import primatives.PointND;
import util.ClusterEdge;

public class Clustering
{
	
	// assuming a and b are of equal dimensions
	private static double distanceND(int dim, PointND a, PointND b)
	{
		double dist = 0;
		for (int i = 0; i < dim; i++)
		{
			dist = a.get_coord(0)*a.get_coord(0) + b.get_coord(i)*b.get_coord(i); 
		}
		return Math.sqrt(dist);
	}
	
	private static PointND bruteforce_findcenter(ArrayList<PointND> cluster, int dim)
	{
		PointND center = new PointND(dim);

		double cx = 0;
		double cy = 0;
		double cz = 0;
		
		for (PointND pt: cluster)
		{
			cx += pt.get_coord(0);
			cy += pt.get_coord(0);
			cz += pt.get_coord(0);
		}
		
		cx /= cluster.size();
		cy /= cluster.size();
		cz /= cluster.size();
		
		center.set_coord(0, cx);
		center.set_coord(1, cy);
		center.set_coord(2, cz);
		return center;
	}
	
	
	/*
	 * eps = eps*min_distance between each z-point
	 * d = d*max_diameter of point cloud
	 */
	public static ArrayList<ArrayList<PointND>> cluster(ArrayList<PointND> elements, int dimension, double eps, double d)
	{
		ArrayList<ArrayList<PointND>> clusters = new ArrayList<ArrayList<PointND>>(); // [i] = ith cluster
		ArrayList<PointND> cluster_centers = new ArrayList<PointND>(); // [i] = center of ith cluster
		final int dim = dimension;
		
		// first sort by dimension
		Collections.sort(elements, new Comparator<PointND>()
		{
		    public int compare(PointND p1, PointND p2)
		    {
		    	Double x1 = p1.get_coord(dim);
		    	Double x2 = p2.get_coord(dim);
		    	return x2.compareTo(x1);
		    }
		});
		
		// now we find the constants
		double min_xdist = Double.MAX_VALUE; // these two will form a rectangle
		double max_xdist = Double.MIN_VALUE; // which d will be a constant factor of
		
		double min_ydist = Double.MAX_VALUE; // these two will form a rectangle
		double max_ydist = Double.MIN_VALUE; // which d will be a constant factor of
		
		double zdist = Double.MIN_VALUE; // eps
		
		for (int i = 0; i < elements.size() - 1; i++)
		{
			PointND current = elements.get(i);
			PointND next = elements.get(i+1);
			
			// d
			double x = Math.abs(current.get_coord(0));
			min_xdist = Math.min(min_xdist, x);
			max_xdist = Math.max(max_xdist, x);
			
			double y = Math.abs(current.get_coord(1));
			min_ydist = Math.min(min_ydist, y);
			max_ydist = Math.max(max_ydist, y);
			
			// eps
			double distz = Math.abs(current.get_coord(2) - next.get_coord(2));
			zdist = Math.max(zdist, distz);
		}
		
		double dx = min_xdist - max_xdist;
		double dy = min_ydist - max_ydist;
		double diameter = Math.sqrt(dx*dx  + dy*dy);
		
		double dz = Math.abs(elements.get(0).get_coord(2) - elements.get(elements.size()-1).get_coord(2)); 
		
		System.out.println("min_dist = " + (zdist));
		System.out.println("diameter = " + (diameter));
		
		System.out.println("eps*min_dist = " + (eps*zdist));
		System.out.println("d*diameter = " + (d*diameter));
		
		int cluster_number = 0;
		for (PointND pt : elements)
		{
			boolean newCluster = true;
			for (int i = 0; i < cluster_number; i++)
			{
				ArrayList<PointND> cluster = clusters.get(i);
				PointND lastClusterPt = cluster.get(cluster.size()-1);
				if (distanceND(dim, lastClusterPt, pt) < d*diameter || Math.abs(lastClusterPt.get_coord(2) - pt.get_coord(2)) < eps*zdist) // part of this new cluster, add it to the cluster and then update the center
				{
					newCluster = false;
					int num = cluster.size(); // number of points currently in the cluster, use it as weighting
					
					System.out.println("cluster " + i + " -> " + num);
					cluster.add(pt);
					break;
				}
				else // not part of this cluster, move on to the next
				{
					
				}
			}
			
			if (newCluster)
			{
				ArrayList<PointND> c = new ArrayList<PointND>();
				c.add(pt);
				clusters.add(c);
				cluster_centers.add(pt);
				cluster_number++;
				
				System.out.println("New Cluster. [" +cluster_number+"]");
			}
			
		}
		
		return clusters;
	}

	/**
	 * Take in a set of points and compute a clustering by dropping the edges which are smaller than eps*length
	 * where length can be the average length, max/min or some other statistic
	 * @param elements
	 * @param eps
	 * @return A clustering based off the MST
	 */
	public static ArrayList<ArrayList<PointND>> mst_cluster(ArrayList<PointND> elements, double eps)
	{
		ArrayList<ClusterEdge> mst = Graphs.MST_Euclidean(elements, 100);
		
		System.out.println("MST Size = " + mst.size());
		
		ArrayList<ArrayList<PointND>> clusters = new ArrayList<ArrayList<PointND>>();
		return clusters;
	}
}
